//冒泡排序
function bubbleSort(arr) {
    var len = arr.length;
    for (var i = 0; i < len; i++) {
        for (var j = 0; j < len - i - 1; j++) {
            if (arr[j] > arr[j + 1]) {
                var temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
            }
        }
    }
    return arr;
}
//测试代码
console.log(bubbleSort([1, 5, 6, 3, 0, 7, 4, 9, 8, 2]));
// 选择排序
function selectionSort(arr) {
    var len = arr.length;
    var minIndx, temp;
    for (var i = 0; i < len - 1; i++) {
        minIndx = i;
        for (var j = i + 1; j < len; j++) {
            if (arr[j] < arr[minIndx]) {
                minIndx = j;
            }
        }
        temp = arr[i];
        arr[i] = arr[minIndx];
        arr[minIndx] = temp;
    }
    return arr;
}

// 测试代码
var arr = [64, 34, 25, 12, 22, 11, 90];
console.log(selectionSort(arr)); // 输出 [11, 12, 22, 25, 34, 64, 90]
//插入排序
function insertionSort(arr) {
    var len = arr.length;
    var temp, j;
    for (var i = 1; i < len; i++) {
        temp = arr[i];
        j = i - 1;
        while (j >= 0 && arr[j] > temp) {
            arr[j + 1] = arr[j];
            j--;
        }
        arr[j + 1] = temp;
    }
    return arr;
}

// 测试代码
var arr = [64, 34, 25, 12, 22, 11, 90];
console.log(insertionSort(arr)); // 输出 [11, 12, 22, 25, 34, 64, 90]
//归并排序
function mergeSort(arr) {
    var len = arr.length;
    if (len < 2) {
        return arr;
    }
    var mid = Math.floor(len / 2);
    var leftArr = arr.slice(0, mid);
    var rightArr = arr.slice(mid);
    return merge(mergeSort(leftArr), mergeSort(rightArr));
}

function merge(leftArr, rightArr) {
    var result = [];
    while (leftArr.length && rightArr.length) {
        if (leftArr[0] <= rightArr[0]) {
            result.push(leftArr.shift());
        } else {
            result.push(rightArr.shift());
        }
    }
    return result.concat(leftArr).concat(rightArr);
}

// 测试代码
var arr = [8, 7, 6, 5, 4, 3, 2, 1];
console.log(mergeSort(arr));
//快速排序
function quickSort(arr) {
    if (arr.length <= 1) {
        return arr;
    }

    const pivot = arr[Math.floor(arr.length / 2)];
    const left = [];
    const right = [];

    for (let i = 0; i < arr.length; i++) {
        if (i === Math.floor(arr.length / 2)) {
            continue;
        }

        if (arr[i] < pivot) {
            left.push(arr[i]);
        } else {
            right.push(arr[i]);
        }
    }

    return [...quickSort(left), pivot, ...quickSort(right)];
}

// 示例用法
const arr = [5, 2, 9, 1, 7, 6, 3];
const sortedArr = quickSort(arr);
console.log(sortedArr);
// 计数排序
function countingSort(arr) {
    const max = Math.max(...arr);
    const count = new Array(max + 1).fill(0);
    const result = new Array(arr.length);

    // 统计每个元素出现的次数
    for (let i = 0; i < arr.length; i++) {
        count[arr[i]]++;
    }

    // 计算每个元素的累积和
    for (let i = 1; i < count.length; i++) {
        count[i] += count[i - 1];
    }

    // 将元素按照累积和排序
    for (let i = arr.length - 1; i >= 0; i--) {
        result[count[arr[i]] - 1] = arr[i];
        count[arr[i]]--;
    }

    return result;
}
const arr = [3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5];
const sortedArrs = countingSort(arr);
console.log(sortedArrs); // [1, 1, 2, 3, 3, 4, 5, 5, 5, 6, 9]
//桶排序
function bucketSort(arr) {
    const bucketSize = Math.floor(arr.length / 2); // 桶的大小
    const buckets = []; // 桶数组

    // 初始化桶数组
    for (let i = 0; i < bucketSize; i++) {
        buckets[i] = [];
    }

    // 将元素分配到桶中
    for (let i = 0; i < arr.length; i++) {
        const bucketIndex = Math.floor(arr[i] / bucketSize);
        buckets[bucketIndex].push(arr[i]);
    }

    // 对每个桶进行排序
    for (let i = 0; i < buckets.length; i++) {
        insertionSort(buckets[i]);
    }

    // 将桶中的元素合并到结果数组中
    const result = [];
    for (let i = 0; i < buckets.length; i++) {
        result.push(...buckets[i]);
    }

    return result;
}

function insertionSort(arr) {
    for (let i = 1; i < arr.length; i++) {
        let j = i;
        while (j > 0 && arr[j] < arr[j - 1]) {
            [arr[j], arr[j - 1]] = [arr[j - 1], arr[j]];
            j--;
        }
    }
}
const arr = [3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5];
const sortedArr1 = bucketSort(arr);
console.log(sortedArr1); // [1, 1, 2, 3, 3, 4, 5, 5, 5, 6, 9]
//基数排序
function radixSort(arr) {
    const max = Math.max(...arr); // 找到数组中的最大值
    const digit = Math.floor(Math.log10(max)) + 1; // 计算最大值的位数

    for (let i = 1; i <= digit; i++) {
        const buckets = Array.from({ length: 10 }, () => []); // 初始化桶数组
        // 将元素分配到桶中
        for (let j = 0; j < arr.length; j++) {
            const digit = Math.floor((arr[j] / Math.pow(10, i - 1)) % 10);
            buckets[digit].push(arr[j]);
        }

        // 将桶中的元素合并到结果数组中
        let k = 0;
        for (let j = 0; j < buckets.length; j++) {
            insertionSort(buckets[j]);
            for (let l = 0; l < buckets[j].length; l++) {
                arr[k] = buckets[j][l];
                k++;
            }
        }
    }

    return arr;
}
function insertionSort(arr) {
    for (let i = 1; i < arr.length; i++) {
        let j = i;
        while (j > 0 && arr[j] < arr[j - 1]) {
            [arr[j], arr[j - 1]] = [arr[j - 1], arr[j]];
            j--;
        }
    }
}
const arr = [3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5];
const sortedArr2 = radixSort(arr);
console.log(sortedArr2); // [1, 1, 2, 3, 3, 4, 5, 5, 5, 6, 9]

